Skip to main content

Intervals

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/solutions/93735/a-concise-template-for-overlapping-interval-problem

Common Tricks

Line Sweep/Difference Array​

  • Lots of interval questions can be solved [[Special Techniques#Difference Array]] by this technique
  • Use this when you need to track changing state over time

https://leetcode.com/problems/my-calendar-ii


Greedy End-Time Pattern​

  • When you need to select intervals without overlap, sorting by end time and being greedy often works best
  • Use this when selecting non-overlapping intervals

https://leetcode.com/problems/meeting-rooms

def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
    if not intervals:
        return True

    intervals.sort()
    prevEnd = intervals[0][1]

    for start, end in intervals[1:]:
        if start < prevEnd:
            return False
        
        prevEnd = max(prevEnd, end)
    
    return True

https://leetcode.com/problems/non-overlapping-intervals

  • Intuition: If we sort by start time: [1,7], [1,3], [2,3], [3,4], [4,5] If we tried the greedy approach of keeping the first interval we see after sorting by start time, we'd keep [1,7] and have to remove ALL other intervals because they overlap with it. The answer would be 4 removals.

If we sort by end time instead: [2,3], [1,3], [3,4], [4,5], [1,7] Now we can keep [2,3], then [3,4], then [4,5] - only needing to remove [1,3] and [1,7]. The answer is 2 removals.

The key insight is that sorting by end time guarantees that when we keep an interval, we're committing to the shortest possible blockage of future space. When we kept [1,7] in the start-time approach, we made a bad choice because we committed to blocking a huge range unnecessarily. By sorting on end time, we ensure we always make the most conservative choice about how much future space we block. This is why sorting by start time fails - it doesn't give us any guarantee about how much future space we might accidentally block with our choices

A good way to decide: Ask yourself "Do I care more about when things begin happening (use start) or when they finish (use end)?" If you need to track ongoing events or merge things, sort by start. If you need to make optimal choices about which intervals to pick, sort by end.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    lastEnd = intervals[0][1]
    count = 0

    for start, end in intervals[1:]:
        if start >= lastEnd:
            lastEnd = end
        else:
            count += 1
    
    return count

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons

  • The key issue with sorting by start points is that we might handle a long interval first (like [1,20] in [[1,20], [2,4], [3,5], [6,8]] ) and make suboptimal decisions. When we shoot an arrow at x=20:
    1. We've "wasted" the coverage area of that arrow
    2. We could have shot that arrow at an earlier point to burst multiple balloons
    3. Now we need separate arrows for each of the smaller intervals
def findMinArrowShots(self, points: List[List[int]]) -> int:
    points.sort(key=lambda t: t[1])

    arrow = 1
    lastArrowPos = points[0][1]

    for start, end in points:
        if start > lastArrowPos:
            arrow += 1
            lastArrowPos = end
    
    return arrow

Merge Pattern​

  • This pattern is useful when you need to combine overlapping intervals
  • Use this when combining overlapping intervals

https://leetcode.com/problems/merge-intervals

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    res = [intervals[0]]

    for start, end in intervals[1:]:
        curInterval = res[-1]
        if start > curInterval[1]:
            res.append([start, end])
        else:
            curInterval = [min(curInterval[0], start), max(curInterval[1], end)]
            res[-1] = curInterval
    
    return res

https://leetcode.com/problems/insert-interval

# Greedy
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    res = []

    for i in range(len(intervals)):
        if newInterval[1] < intervals[i][0]:
            res.append(newInterval)
            return res + intervals[i:]
        elif newInterval[0] > intervals[i][1]:
            res.append(intervals[i])
        else:
            newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
    res.append(newInterval)
    
    return res

# Search and insert
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        insertPos = 0
        res = []

        # Search for insert position and add intervals if possible
        while insertPos < len(intervals) and intervals[insertPos][1] < newInterval[0]:
            res.append(intervals[insertPos])
            insertPos += 1
        
        # Resolve overlapping
        while insertPos < len(intervals) and newInterval[1] >= intervals[insertPos][0]:
            newInterval = [
                min(intervals[insertPos][0], newInterval[0]),
                max(intervals[insertPos][1], newInterval[1])
            ]
            insertPos += 1
        res.append(newInterval)
        res += intervals[insertPos:]

        return res

Priority Queue​


https://leetcode.com/problems/meeting-rooms-ii


https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended

 def maxEvents(self, events: List[List[int]]) -> int:
    events.sort()
    endDay = max([event[1] for event in events])
    eventIndex = 0
    heap = []
    count = 0

    for day in range(1, endDay + 1):
        while eventIndex < len(events) and events[eventIndex][0] == day:
            heapq.heappush(heap, events[eventIndex][1])
            eventIndex += 1
        
        while heap and heap[0] < day:
            heapq.heappop(heap)
        
        if heap:
            heapq.heappop(heap)
            count += 1

    return count
  • When intervals are sorted, can use binary search for quick lookups
  • Use this when working with sorted intervals

Problems

https://leetcode.com/problems/employee-free-time